package com.sean.sort;

public class IndexSort {
    public static void indexSort(int[] array){
        long start = System.nanoTime();
        int[] indexArray = new int[array.length];
        for(int i = 0; i < array.length; i++){
            indexArray[i] = i;
        }
        // 插入排序
        for(int i = 1; i < array.length; i++){
            int j = i - 1;
            int temp = array[indexArray[i]];
            int tempIndex = indexArray[i];
            while(j >= 0 && array[indexArray[j]] > temp){
                indexArray[j + 1] = indexArray[j];
                j --;
            }
            indexArray[j + 1] = tempIndex;
        }
        adjustArray(array, indexArray);
        long end = System.nanoTime();
        System.out.println("索引排序用时： " + (end - start) + "ns");
    }

    private static void adjustArray(int[] array, int[] indexArray){
        for(int i = 0; i < array.length; i++){
            int j = i;
            int temp = array[i];
            while(indexArray[j] != i){
                int k = indexArray[j];
                array[j] = array[k];
                indexArray[j] = j;
                j = k;
            }
            array[j] = temp;
            indexArray[j] = j;
        }
    }

    public static void main(String[] args) {
        final int _10w = 100000;
        // 索引排序用时： 2657933000ns
//        int [] test1 = new int[_10w];
//        for(int i = _10w, j = 0; i > 0; i--, j++){
//            test1[j] = i;
//        }
        int[] test1 = {6, 5, 4, 3, 2, 1};
        IndexSort.indexSort(test1);
    }
}
